#!/usr/bin/python

import time, sys
from math import sqrt, ceil, floor, log10

""" 
The Fibonacci sequence is defined by the recurrence relation:

fn = fn1 + fn2, where F1 = 1 afnd F2 = 1.
Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?
    
"""

def main():
    start = time.time()
    
    a, b, fn = 0, 1, 1 
    print 'F1 = 1'
    print 'F2 = 1' 
    
    while True:
        a, b, fn = b, a + b , fn + 1 
        if fn < 13:
            print 'F{0} = {1:4} {2:4}'.format(fn, b, len(str(b)))
        elif fn < 100 and fn % 10 == 0:
            print 'F{0} = {1:4} {2:4}'.format(fn, b, len(str(b)))            
        if len(str(b)) == 1000:
            break
        if b >= 10**999: 
            break 
    
    print 'F{0} = {1:4}'.format(fn - 1, len(str(a))) 
    print 'F{0} = {1:4}'.format(fn, len(str(b)))
    
    print '{0:.2f} s'.format(time.time() - start)  


    
    
if __name__ == '__main__':
  main()

######################################################
#first solution
  
    # fn, a, b = 2, 1, 1
    # print 'F1 = 1'
    # print 'F2 = 1' 
 
    # while True:
        # fn, a, b = fn + 1, b, a + b 

        # if fn < 13:
            # print 'F{0:4} = {1:4} {2:4.2f} {3:4}'.format(fn, b, log10(b), int(log10(b)) + 1)
        # elif fn < 100 and fn % 10 == 0:
            # print 'F{0:4} = {1:4} {2:4.2f} {3:4}'.format(fn, b, log10(b), int(log10(b)) + 1)            
        # if ((int(log10(b))) + 1) == 1000:
            # break
    
    # print 'F{0:4} = {1:4} {2:4.2f} {3:4}'.format(fn - 1, 'fn', log10(a), int(log10(a)) + 1) 
    # print 'F{0:4} = {1:4} {2:4.2f} {3:4}'.format(fn, 'fn', log10(b), int(log10(b)) + 1)  
    
    # F4782 is first with 1000 digit places
    # 0.02 s

# solution 2: using len instead og log10
    # fn, a, b = 2, 1, 1
    # print 'F1 = 1'
    # print 'F2 = 1' 
 
    # while True:
        # fn, a, b = fn + 1, b, a + b 
        # if fn < 13:
            # print 'F{0} = {1:4} {2:4}'.format(fn, b, len(str(b)))
        # elif fn < 100 and fn % 10 == 0:
            # print 'F{0} = {1:4} {2:4}'.format(fn, b, len(str(b)))            
        # if len(str(b)) == 1000:
            # break
    
    # print 'F{0} = {1:4}'.format(fn - 1, len(str(a))) 
    # print 'F{0} = {1:4}'.format(fn, len(str(b)))
    
    # F4782 is first with 1000 digit places
    # 0.46 s  SLOWER!!